01 Najblizi

Систем за праћење температуре током дана бележи вредности у одређеним тренуцима (у минутима од почетка дана). Дат је низ временских тренутака T₁, T₂, …, T_n и одговарајуће температуре A₁, A₂, …, A_n. Затим је дат низ упита Q₁, Q₂, …, Q_m који представљају тренутке у којима желимо да знамо које је било најближе мерење температуре.

За сваки упит Q_i, потребно је пронаћи температуру A_j чији је временски тренутак T_j тренутку Q_i. Ако постоје два мерења једнако удаљена од тренутка Q_i, узима се оно са T_j. Тражена временска сложеност је О(mlogn), а просторна је О(n).

Улаз

• Први ред садржи цео број n ≤ 10⁵ — број мерења.

• Други ред садржи n целих бројева T₁, T₂, …, T_n (сортиран низ времена мерења, у минутима).

• Трећи ред садржи n реалних бројева A₁, A₂, …, A_n (температуре у ^∘C).

• Четврти ред садржи цео број m ≤ 10⁵ — број упита.

• Пети ред садржи m целих бројева Q₁, Q₂, …, Q_m.

Излаз

Исписати m реалних бројева (температура), сваки у посебном реду – одговарајућу температуру најближег мерења за сваки упит Q_i.

Пример

Улаз

5
10 40 80 120 200
18.5 19.0 21.2 22.0 23.5
3
15 100 190

Излаз

18.5
21.2
23.5